package alo.p4.work;

import org.junit.Test;
public class InToPost {

    @Test
    public void test(){
        Solution solution=new Solution();
        String s = solution.InToPost("A*B-(C+D)+E");
        System.out.println(s);//AB*CD+-E+

    }


    //中缀表达式转换为后缀表达式
     class Solution{
        String InToPost(String input){
            String output = "";
            int stackSize = input.length();
            Stack theStack = new Stack(stackSize);
            for (int j = 0; j < input.length(); j++) {
                char ch = input.charAt(j);
                //如果是一个操作数
                if(isNoL(ch))
                    output=output+ch;
                //如果是一个右括号
                else if (ch==')'){
                    while (theStack.peek()!='('){
                        output=output+theStack.pop();
                    }
                    theStack.pop();
                //是一个操作符或左括号
                }else {
                    //直到栈里出现比t的优先级小的括号，或者出现一个左括号，或者栈空
                    while (!theStack.isEmpty()  && theStack.peek()!='('  &&  (gotOper(ch)<=gotOper(theStack.peek()))){
                        output=output+theStack.pop();
                    }
                    theStack.push(ch);
                }
            }
            //把剩下的符号出栈
            output=output+theStack.pop();
            return output;
        }
         //是否为数字或字母
         boolean isNoL(char ch){
             if ((ch>='0'&&ch<='9')||(ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z')){
                 return true;
             }
             return false;
         }
         //判断级别
         public int gotOper(char opThis) {
             int i;
             if (opThis == '+' || opThis == '-')
                 i = 1;
             else
                 i = 2;
             return i;
         }
    }


    //栈结构，简单数组实现
    class Stack {
        private int maxSize;
        private char[] stackArray;
        private int top;
        public Stack(int max) {
            maxSize = max;
            stackArray = new char[maxSize];
            top = -1;
        }
        public void push(char j) {
            stackArray[++top] = j;
        }
        public char pop() {
            return stackArray[top--];
        }
        public char peek() {
            return stackArray[top];
        }
        public boolean isEmpty() {
            return (top == -1);
        }
    }
}